﻿//给一个01矩阵，1代表是陆地，0代表海洋， 如果两个1相邻，那么这两个1属于同一个岛。
//我们只考虑上下左右为相邻。
//岛屿 : 相邻陆地可以组成一个岛屿（相邻:上下左右） 判断岛屿个数。
//例如：
//输入
//[
//        [1, 1, 0, 0, 0],
//        [0, 1, 0, 1, 1],
//        [0, 0, 0, 1, 1],
//        [0, 0, 0, 0, 0],
//        [0, 0, 1, 1, 1]
//]
//对应的输出为3

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 判断岛屿数量
     * @param grid char字符型vector<vector<>>
     * @return int整型
     */
    void dfs(vector<vector<char>>& num, int x, int y)
    {
        int m = num.size(), n = num[0].size();
        // if(x+1<m&&y+1<n)  num[x][y]=num[x+1][y]=num[x][y+1]='0';
        // if(x+1==m&&y+1<n) num[x][y]=num[x][y+1]='0';
        // if(x+1<m&&y+1==n) num[x][y]=num[x+1][y]='0';
        // if(num[x+1][y+1]=='1') dfs(num,x+1,y+1);
        num[x][y] = '0';
        if (y + 1 < n && num[x][y + 1] == '1') dfs(num, x, y + 1);//检查右边
        if (y - 1 >= 0 && num[x][y - 1] == '1') dfs(num, x, y - 1);//检查左边
        if (x + 1 < m && num[x + 1][y] == '1') dfs(num, x + 1, y);//检查下边
        if (x - 1 >= 0 && num[x - 1][y] == '1') dfs(num, x - 1, y);//检查上边
        //if(x+1<m&&y-1>=0&&num[x+1][y-1]=='1') dfs(num,x+1,y-1);//检查左下
        //if(x+1<m&&y+1<n&&num[x+1][y+1]=='1') dfs(num,x+1,y+1);//检查右下
        //if(x-1>=0&&y-1>=n&&num[x-1][y-1]=='1') dfs(num,x-1,y-1);//检查左上
        //if(x-1>=0&&y+1<n&&num[x-1][y+1]=='1') dfs(num,x-1,y+1);//检查右上
    }
    int solve(vector<vector<char> >& grid) {
        // write code here
        int ret = 0;
        //int m=grid.size(),n=grid[0].size();
        for (int i = 0; i < grid.size(); i++)
        {
            for (int j = 0; j < grid[i].size(); j++)
            {
                if (grid[i][j] == '1')
                {
                    ret += 1;
                    dfs(grid, i, j);
                }
            }
        }
        //cout<<ret<<endl;
        return ret;
    }
};

/////////////////////////////////////////////////////////////////////////////
class Solution {
public:
    int solve(vector<vector<char>>& grid) {
        int ret = 0; // 记录最终结果
        int m = grid.size(), n = grid[0].size();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    ret++; // 发现⼀个岛屿
                    dfs(grid, i, j); // 把这个岛屿全部修改成 '0'
                }
            }
        }
        return ret;
    }
    int dx[4] = { 0, 1, -1, 0 };
    int dy[4] = { 1, 0, 0, -1 };
    void dfs(vector<vector<char>>& grid, int i, int j) {
        grid[i][j] = '0'; // 把该位置先变成 '0'
        int m = grid.size(), n = grid[0].size();
        // 遍历相邻的所有位置
        for (int k = 0; k < 4; k++) {
            int x = i + dx[k], y = j + dy[k];
            if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1')
                dfs(grid, x, y);
        }
    }
};